In step with the rapid evolution of information technology, modern computer systems are expected to store and exchange ever-increasing amounts of data and, accordingly, the efficient management of data by these systems is of paramount importance. The delay associated with searching a database and/or inserting data thereinto are often times a significant source of latency associated with the transmission of data within a computer network—e.g., the Internet—and a failure to efficiently manage a database may produce a bottleneck in the flow of data across a network. For example, network switches and routers maintain a database of IP (Internet Protocol) addresses, and each IP address may have a corresponding action or rule that is to be applied to any data packet sharing that IP address. By way of example, a rule may comprise a network address translation, a routing decision (e.g., which port to direct a packet), a priority determination, or a filtering function. When a switch or router receives a packet having an IP address, the switch or router may search its IP address database to determine which action is to be taken with respect to that packet.
A database may comprise a series of sequentially stored data entries—e.g., IP addresses—of a given depth. The time necessary to search such a sequential database is generally proportional to the database's depth. For example, if there are 100 entries in a sequential database, a search of the database may require 100 clock cycles. Thus, a sequential database is unsuitable for all but the smallest database applications, as there is a high latency required for these sequential searches.
An alternative solution was to use a set-associative cache. The cache was partitioned into a plurality of sections, each section capable of storing the same fixed number of data entries, and the size of these sections could not be expanded. Thus, storage space within a section could not be guaranteed and, if insertion of a data entry was attempted at a full section, a “collision” of data entries would occur. Such a collision usually resulted in the loss of data, as the newly inserted data entry could displace an existing entry or the new data itself could be lost. Also, the use of a plurality of fixed-sized sections resulted in a significant amount of unutilized memory. In sum, use of a set-associative cache for a database is inefficient and susceptible to data loss. Managing these data losses, as well as the failure to fully utilize available memory, increases the memory overhead associated with a set-associative cache database.
Another solution was to use a content-addressable memory, or CAM. A CAM provides a data structure wherein the entries are stored sequentially, but the CAM includes logic circuitry that enables a parallel search of the sequentially stored data entries. Thus, the use of a CAM overcomes the latency associated with traditional sequential databases and, further, does not suffer from the collision and data loss problems exhibited by set-associative caches. A CAM does, however, have some significant drawbacks. Specifically, CAMs come at a high cost, both monetarily and in terms of the on-chip real estate required for the above-described logic circuitry. Also, CAMs are unsuitable for databases having a large number of entries.
As information technology, as well as computer networking technology, continue to evolve, ever-increasing amounts of data will need to be managed. For example, the next generation of hardware-based network switches and routers will be expected to handle an IP address database having greater than one million entries. Such next-generation networking components, as well as other database systems, will require efficient, low memory overhead database systems that maintain data integrity (e.g., no data collisions) while handling a large number of data entries. Current hardware-based solutions—e.g., sequential databases, set-associative caches, and content-addressable memories, all as described above—will not meet the demands of these next-generation systems.